﻿// .cpp    .cc     .cxx 后缀的文件都是 C++ 文件


// 快速排序：
//给定你一个长度为 n 的整数数列。
//
//请你使用快速排序对这个数列按照从小到大进行排序。
//
//并将排好序的数列按顺序输出。
//
//输入格式
//输入共两行，第一行包含整数 n。
//
//第二行包含 n 个整数（所有整数均在 1∼109 范围内），表示整个数列。
//
//输出格式
//输出共一行，包含 n 个整数，表示排好序的数列。
//
//数据范围
//1≤n≤100000
//输入样例：
//5
//3 1 2 4 5
//输出样例：
//1 2 3 4 5

//
//#include <iostream>
//#include <cstring>
//#include <algorithm>
//
//using namespace std;
//
//const int N = 100010;
//int arr[N];
//
//void my_qsort(int left, int right) {
//	if (left >= right) return;
//
//	int target = arr[left + right >> 1], pre = left - 1, cur = right + 1;
//	while (pre < cur) {
//		do {
//			pre++;
//		} while (arr[pre] < target);
//		do {
//			cur--;
//		} while (arr[cur] > target);
//		
//		if (pre < cur)
//			swap(arr[pre], arr[cur]);
//	}
//
//	my_qsort(left, cur);
//	my_qsort(cur + 1, right);
//}
//
//int main(void) {
//	int n;
//	cin >> n;
//	for (int i = 0; i < n; i++) cin >> arr[i];
//
//	my_qsort(0, n - 1);
//
//	for (int i = 0; i < n; i++) cout << arr[i] << ' ';
//
//	return 0;
//}